Processus de décision Markovien (Markov Decision Process - MDP)

3. Formulation Mathématique des MDP

Un processus de décision Markovien est un ensemble composé de 4 classes $\left( {S,A,P,R} \right)$ avec:

• Un ensemble fini d'états $s \in S$
• Un ensemble fini d'action $a \in A$
• Probabilités de transitions $p \in P$ : $p\left( {s'|s,a} \right) = \Pr \left\{ {{S_{t + 1}} = s'|{S_t} = s,{A_t} = a} \right\}$

• Récompenses $r \in R$ obtenues suite aux transitions :

  • Récompense suite à une paire Etat - Action : $r\left( {s,a} \right) = {\rm E}\left[ {{R_{t + 1}}|{S_{t}} = s,{A_t} = a} \right]$
  • Récompense suite à au triplé Etat - Action - Etat suivant : $r\left( {s,a,s'} \right) = {\rm E}\left[ {{R_{t + 1}}|{S_{t}} = s,{A_t} = a,{S_{t + 1}} = s'} \right]$

• $S$ est l'espace des états contenant l'ensemble des états possibles

• $A$ est l'espace des actions contenant l'ensemble des actions possibles
• $P$ est l'espace des probabilités des transitions
  • $p\left( {s'|s,a} \right) = \Pr \left\{ {{S_{t + 1}} = s'|{S_t} = s,{A_t} = a} \right\}$ est la probabilité que l'agent aille sur l'état $s'$ sachant qu'il est sur l'état $s$ et qu'il effectue l'action $a$
• $R$ est l'espace des récompenses immédiates obtenues lors des transitions

 

La somme des probabilités qu'un agent aille atterrisse sur un état (peu importe lequel - cela peut être le même que l'état initial) quelque soit l'action choisie est égale à 1. Cela revient à dire que l'agent transite toujours (encore une fois, cela peut être sur le même état) :

$$\sum\limits_{s' \in S} {p\left( {s'|s,a} \right)} = 1$$

L'équation fondamentale dans l'apprentissage par renforcement est la suivante:

$$p\left( {s',r|s,a} \right) = P\left( {{S_{t + 1}} = s',{R_{t + 1}} = r|{S_t} = s,{A_t} = a} \right)$$

C'est la probabilité que l'agent aille sur l'état suivant $s'$ à l'instant $t+1$ et gagne la récompense $r$ alors qu'il est sur l'état $s$ et qu'il effectue l'action $a$ à l'instant $t$.

Il est également important de remarquer que chaque instant suivant $s'=s_{t+1}$ sur lequel l'agent transite ne dépend que de l'état initial $s_t$ et de l'action choisie $a_t$.